package com.darrenchan.leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2019-12-29 23:01
 */
public class Q69 {
    public int mySqrt(int x) {
        if (x == 0 || x == 1) {
            return x;
        }
        long start = 0, end = x / 2;
        while (start + 1 < end) {
            long mid = start + (end - start) / 2;
            if (mid * mid < x) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (x < start * start) {
            return (int) (start - 1);
        } else if (x >= start * start && x < end * end) {
            return (int) (start);
        } else {
            return (int) (end);
        }
    }


    public int sqrt(int x) {
        if(x == 0 || x == 1) {
            return x;
        }

        long start = 0, end = x / 2;
        while(start + 1 < end) {
            long mid = start + (end - start) / 2;
            if(mid * mid <= x) {
                start = mid;
            } else {
                end = mid;
            }
        }

        return (int) start;
    }


    public static void main(String[] args) {
        System.out.println(new Q69().sqrt(4));
        Queue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
    }
}
